Leetcode刷题记录(Java)

发表于 | 更新于: | 分类于
Problem 392 Is Subsequence/Problem 401 Binary Watch/Problem 404 Sum of Left Leaves

Problem 392 Is Subsequence
ngyeRf.png
该问题属于字符串问题,判断一个字符串是否是另一个字符串的子串,子串的定义是字符串a是否与字符串b在去除某些字母后相同

主要思路:
该题分为以下几种情况

  • 子串s比主串t长,此时直接返回false
  • 子串s和主串t长度相同,此时比较两者是否相同
  • 子串s比主串t短,此处我采用了比较暴力的循环处理,将子串s拆解成字符数组,并循环,将每个字符与主串中的字符进行匹配,如果匹配上则将该下标加入list,并将下标赋值给循环变量,这样就不用回头,而是以匹配点为起点继续后续匹配,全部结束后得到list,此时用list长度和子串比较,如果全部都存在的话,则两者必然长度相同,第二步就是检查list中值前后的大小,由于该题要求相对顺序不能改变,所以遍历一遍后即可判断.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length()>t.length())
            return false;
        if(s.length()==t.length()){
            return s.equals(t);
        }
        char[] s_char = s.toCharArray();
        char[] t_char = t.toCharArray();
        List<Integer> list =new ArrayList<>();
        int nowIndex = 0;
        for (char c : s_char) {
            for (int j = nowIndex; j < t_char.length; j++) {
                if (t_char[j] == c) {
                    nowIndex = j+1;
                    list.add(nowIndex);
                    break;
                }
            }
        }
        if(list.size()<s.length())
            return false;
        for (int i=0;i<list.size()-1;i++){
            if(list.get(i)>list.get(i+1))
                return false;
        }
        return true;
    }
}

注意事项:

  • 在赋值时记得坐标+1

Problem 401 Binary Watch
ng6BjS.png
该问题比较有意思,开始思考的时候认为会涉及到很多排列组合,还感到比较复杂,最后借鉴了别人的答案,时间和空间效率都比较好.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        String[][] hours = {{"0"}, {"1","2","4","8"}, {"3","5","6","9","10"},{"7","11"} };
        String[][] minutes = {
            {"00"}, // 0 bits on
            {"01","02","04","08","16","32"}, // 1 bit on
            {"03","05","06","09","10","12","17","18","20","24","33","34","36","40","48"}, // 2 bits on
            {"07","11","13","14","19","21","22","25","26","28","35","37","38","41","42","44","49","50","52","56"}, // 3 bits on
            {"15","23","27","29","30","39","43","45","46","51","53","54","57","58"}, // 4 bits on
            {"31","47","55","59"} // 5 bits on
        };
        for(int i = 0; i <= 3 && i <= num; i++) { 
            if(num-i <= 5) {
                for(String hour : hours[i]) {
                    for(String min : minutes[num-i]) {
                        res.add(hour + ":" + min);
                    }
                }
            }
        }
        
        return res;
    }
}

代码说明:
这份代码主要是做了定界的工作,把表盘分为上下两部分,单独把时针和分针的所有情况列出来,也就是说当数字大于3的时候,时针已经超过11,剩下的应该是分针,此时只要遍历将所有组合拼凑起来即可.

Problem 404 Sum of Left Leaves
ng2nts.png
该问题是二叉树相关问题,求所有左叶子结点的值的和.对此我使用了几个辅助函数:

  • 判断当前结点的左结点是不是左叶子结点
  • 判断树的深度

判断结点是否为左叶子结点很好理解,如果能判断的话,就能以此为依据对所有结点进行遍历,对于满足条件的结点进行累加即可.而判断树的深度是为了防止树的深度只有1的情况,因为当只有根结点的时候应该返回0.有了这两个条件为基础就能对树进行遍历

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int left = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null) return 0;
        if(depth(root)==1)
            return 0;
        else{
            if(isLeftLeafNode(root,root.left)){
                left += root.left.val;
            }
            sumOfLeftLeaves(root.left);
            sumOfLeftLeaves(root.right);  
        }
        return left;
    }

    public boolean isLeftLeafNode(TreeNode root,TreeNode leaf){
        return root.left==leaf&&leaf!=null&&leaf.left==null&&leaf.right==null;
    }
    public int depth(TreeNode root){
        if(root==null)
            return 0;
        return 1+Math.max(depth(root.left),depth(root.right));
    }
}